package cn.edu.gxnu.dsa.sort;

import cn.edu.gxnu.dsa.list.SqList;

public class SqListWithSort extends SqList {

	public SqListWithSort(int maxSize) {
		super(maxSize);
	}

	public void sortWithGuard() {
		Object[] temp = spreadAarry(this.getListElement());

		for (int i = 1, j = 0; i < this.length() + 1; i++) {
			temp[0] = temp[i];
			for (j = i - 1; ((IntType) temp[0]).compareTo((IntType) temp[j]) < 0; j--) {
				temp[j + 1] = temp[j];
			}
			temp[j + 1] = temp[0];
		}

		setArray(temp);
	}

	public void quickSort() {
		try {
			qSort(0,(this.length()-1));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private void qSort(int low, int high) throws Exception {		
		if (low < high) {
			int pivotLoc = partition(low, high);
			qSort(low, pivotLoc - 1);
			qSort(pivotLoc + 1, high);
		}
	}

	private int partition(int low, int high) throws Exception {
		Object pivot = this.get(low);
		while (low < high) {
			while ((low < high) && ((IntType) pivot).compareTo((IntType) this.get(high)) <= 0) {
				high--;
			}

			if (low < high) {
				set(low, this.get(high));
				low++;
			}

			while (low < high && ((IntType) pivot).compareTo((IntType) this.get(low)) > 0) {
				low++;
			}

			if (low < high) {
				set(high, this.get(low));
				high--;
			}
		}

		set(low, pivot);
		return low;
	}

	private void set(int index, Object obj) {
		(this.getListElement())[index] = obj;
	}

	private Object[] spreadAarry(Object[] originalArray) {
		Object[] array = new Object[originalArray.length + 1];
		for (int i = 1; i < array.length; i++) {
			array[i] = originalArray[i - 1];
		}
		return array;
	}

	private void setArray(Object[] processedArray) {
		Object[] array = new Object[processedArray.length - 1];
		for (int i = 0; i < array.length; i++) {
			array[i] = processedArray[i + 1];
		}
		this.setListElement(array);
	}

}
